Structures de données abstraites & Graphes II : parcours en largueur

Table des matières

1. Piles et files
2. Parcours en largeur d'un graphe
- 2.1. Rappels sur le parcours en profondeur
- 2.2. Parcours en largeur

1. Piles et files

Les piles et les files sont deux modèles théoriques de structures de données mutables. Elles représentent un ensemble de données, que l'on peut modifier avec deux opérations fondamentales : l'ajout d'un élément et le retrait d'un élément (non choisi).

Elles diffèrent dans la spécification de l'élément qui est retiré.

1.1. Piles

Quand on retire un élément d'une Pile, l'élément retiré est le dernier à avoir été ajouté. On utilise parfois la terminologie LIFO, pour «Last In, First Out».

Les listes de Python sont un modèle de pile. On peut ajouter un élément avec l'instruction l.append(e) et retirer le dernier élément avec l'instruction l.pop().

Figure 1 : Une pile d'assiettes

Les extraits suivants implémentent une fine abstraction par-dessus les listes Python.

# Renvoie une nouvelle pile vide
def nouvelle_pile():
    return []

# Renvoie le nombre d'éléments de la pile
def longueur(pile):
    return len(pile)

# Ajoute l'élément e à la pile
def empile(pile, e):
    pile.append(e)

# Retire le dernier élément de la pile, et le renvoie
# Donne une erreur si la pile est vide
def depile(pile):
    return pile.pop()

Souvent, on rajoute également une méthode peek pour voir quel est l'élément en haut de la pile, sans le retirer.

# Renvoie la valeur de l'élément en haut de la pile
def peek(pile):
    if len(pile) > 0:
        return pile[len(pile)-1]
    else:
        return None

Écrire une fonction tri_pile qui prend en argument une pile p implémentant les méthodes décrites plus haut, et renvoie une nouvelle pile, avec les mêmes éléments que p, mais triée. On autorise la modification de la pile d'origine, mais aucune autre structure de donnée que la pile d'origine, et une seconde pile qui sera renvoyée.

On utilisera uniquement les cinq méthodes écrites plus haut, et aucune opération directement sur des listes.

★ Application : expressions parenthésées

On considère une chaîne de caractères c avec entre autres des caractères "(" et ")".

On suppose que le premier et le dernier caractère de c sont "(" et ")".

Écrire une fonction bien_parenthesee qui prend en argument la chaîne c et qui renvoie True si l'expression est bien parenthésée.

Par exemple l'expression "(c(a)(a(b)))" est bien parenthésée, alors que ")(b(a)" ne l'est pas.

On appelle sous-expression de c toute tranche c[i:j] de c délimitée par deux parenthèses "(" et ")" qui correspondent l'une à l'autre, c'est-à-dire telle que c[i:j] soit elle-même bien parenthésée. On dit que cette sous-expression est à l'indice $i$.

Les sous-expressions se contiennent les unes les autres, ce qui induit une hiérarchie.

Écrire une fonction parenté qui prend en argument la chaîne c, de taille $n$, supposée bien parenthésée et renvoie deux listes parent, et enfants.

Pour chaque indice $i\in\db{0,n-1}$ auquel commence une sous-expression $E$ (c'est-à-dire tel que c[i] == "(").
- parent[i] contiendra l'indice de la plus petite sous-expression contenant strictement la sous-expression $E$.
- enfants[i] contiendra la liste des indices des sous-expressions qui sont contenues dans $E$.
Pour les autres indices, et pour la toute première parenthèse ouvrante, on utilisera la valeur $-1$ dans parent, et une liste vide dans enfants.

Au fil de la lecture, on maintiendra une pile contenant les indices des parenthèses ouvertes lues qui n'ont pas encore été fermées.
Réciproquement, on suppose connues les listes parent et enfants, et on veut reconstituer une expression correspondante, que l'on construira comme une liste, formée des caractères "(" et ")".

Écrire une telle fonction expression avec comme arguments parent et enfants.

On pourra utiliser une liste prochain_enfant initialisée à [0] * n pour retenir, pour chaque $i$, quel est le prochain enfant de l'expression d'indice $i$ à visiter.

1.2. Files

Quand on retire un élément d'une File, l'élément retiré est le premier à avoir été ajouté (parmi les éléments restant). On utilise parfois la terminologie FIFO, pour «First In, First Out».

Quand on ajoute un élément, on le rajoute à la «fin» de la file.

Figure 2 : Une file d'attente

1.2.1. Première implémentation non efficace

On peut choisir de représenter une file par une liste, dont le dernier élément est en tête de la file.

Pour défiler un élément (le retirer de la file), il suffit de retirer le dernier élément de la liste. Par contre, pour enfiler (ajouter) un élément, il faut le mettre au début de la liste, ce qui nécessite de décaler les autres éléments.

def nouvelle_file():
    return []

def longueur_file(file):
    return len(file)

def defile(file):
    return file.pop()

def enfile(file, e):
    file.append(e)
    i = len(file) # Position de l'élément e dans la liste
    while i != 0:
        l[i], l[i-1] = l[i-1], l[i]
        i -= 1

La fonction enfile a une complexité linéaire en la taille de la file, ce qui n'est pas satisfaisant.

Deuxième implémentation naïve

On propose une nouvelle implémentation d'une file en utilisant les listes de Python. Les éléments de la file seront stockés à des indices consécutifs d'une liste l, du premier au dernier, et l[0] contiendra l'indice du premier élément de la file dans l.

Par exemple, une file contenant dans cet ordre trois éléments "A", "B" et "C" pourra être représentée par la liste

l = [4, *, *, *, "A", "B", "C"]

où les * représentent des valeurs quelconques.

Après l'ajout d'un élément "D", la file sera représentée par la liste

[4, *, *, *, "A", "B", "C", "D"]

Après le retrait du premier élément, "A", la file sera représentée par la liste

[5, *, *, *, "A", "B", "C", "D"]      =      [5, *, *, *, *, "B", "C", "D"]

La liste vide n'est pas une représentation valide d'une file.

Implémenter des fonctions longueur (qui renvoie le nombre d'éléments de la file), enfile, défile et nouvelle_file.

Par rapport à l'implémentation précédente, pour celle-ci, toutes les opérations élémentaires ont des complexité en $O(1)$.

L'inconvénient de cette implémentation est qu'au fur et à mesure de l'utilisation d'une file, la liste sous-jacente pourrait devenir arbitrairement longue, même si la file ne contient que peu d'éléments.

Si une liste représente une file, contracter cette liste consiste à la modifier, de sorte qu'elle représente toujours la même file, mais en minimisant la longueur de la liste.

Écrire une fonction contracte_peut_être qui prend en argument une liste représentant une file et contracte cette liste, seulement si elle a une longueur strictement supérieure au double du nombre d'éléments de la file.

Si on contractait la liste à chaque appel défile, la complexité de défile serait en $O(n)$, où $n$ est la taille de la file.
En ajoutant un appel contracte_peut_être dans la fonction défile, sa complexité reste en $O(n)$ dans le pire des cas, mais on peut justifier qu'en moyenne, sa complexité est en $O(1)$.

Le module `collections.deque`

Python propose une implémentation toute prête d'une file, qui s'utilise comme suit.

from collections import deque
file = deque()   # crée une nouvelle file
file.append("A") # Opération en temps constant O(1)
file.append("B")
file.append("C")
file.popleft()   # Renvoie "A", en temps constant O(1)
file.popleft()   # Renvoie "B"
len(file)        # Renvoie 1

Le module deque implémente en fait une structure de donnée plus générale qu'une file et supporte également les opérations append_left, pop (en $O(1)$) et un test d'appartenance via e in file, avec une complexité linéaire.

1.3. File de priorité

Une file de priorité est une structure de données théorique qui stocke des couples $(d, p)$, ou $d$ représente une donnée et $p$ représente un poids (ou une priorité).

Les opérations élémentaires sont

l'ajout d'une nouvelle donnée $d$, avec un poids $p$.
le retrait de la donnée de poids minimal (ou de priorité maximale)

Implémentation naïve

On va implémenter une structure de file de priorité à l'aide des dictionnaires de Python, dont les clés seront les données, et les valeurs leurs priorités.

On rappelle que si dic est un dictionnaire,

len(dic) renvoie le nombre de clés du dictionnaire,
On peut tester l'existence d'une clé e dans le dictionnaire via e in dic.
Si e est une clé du dictionnaire, dic.pop(e) supprime cette clé.
On peut itérer sur toutes les clés du dictionnaire via for e in dic.

Écrire une fonction insert qui prend en argument un dictionnaire, une donnée d et un poids p, et rajoute ce couple au dictionnaire.
Écrire une fonction retire_min qui prend en argument le dictionnaire dico, que l'on suppose non vide, renvoie le couple (d, p) de poids minimal du dictionnaire, et supprime cette donnée du dictionnaire.

L'implémentation choisie a les conséquences suivantes, qui ne sont pas propres aux files de priorités en général.

Une même donnée ne peut pas apparaître plusieurs fois dans la file.
On peut tester l'appartenance d'une donnée e à la file via e in d.
On peut modifier la priorité d'une donnée de la file.

L'inconvénient de l'implémentation est que la fonction retire_min a une complexité en $O(n)$, où $n$ est le nombre d'éléments dans la file. Il existe des implémentations plus efficaces pour laquelle cette opération a une complexité en $O(\ln n)$.

★ Implémentation par tas

On propose d'implémenter une file de priorité efficace en utilisant un tas.

Un tas est une structure de donnée représentant un arbre binaire dont les sommets sont étiquetés par un entier, vérifiant les deux propriétés suivantes

l'arbre doit être presque complet : tous les niveaux sont complets, sauf le dernier, qui est rempli à gauche.
l'arbre doit être ordonné, au sens où l'entier de tout sommet doit être supérieur aux entiers de ses fils.

On représente enfin ce tas en python à l'aide d'une liste d'entiers l, de sorte que l[0] soit l'entier de la racine de l'arbre, et pour tout indice i, l[2i+1] et l[2i+2] soient les étiquettes des deux fils du sommet d'étiquette l[i].

Ici, le tas représente une file de priorité qui ne contient pas de données, uniquement les priorités.

Écrire une fonction insert qui prend en argument un tas et un entier, et insert cet entier dans le tas. On commencera par placer cet entier à la fin de la liste, ce qui invalide la propriété d'ordre de l'arbre, puis, par des échanges successifs, on remontera cet entier dans l'arbre jusqu'à ce que la propriété d'ordre soit vérifiée.

Justifier que la complexité de insert est en $O(\ln n)$.
Écrire une fonction retire_max qui prend en argument un tas et retire et renvoie le maximum du tas. Pour préserver les propriétés du tas, on commencera par mettre le dernier élément du tas à la racine, puis par des échanges successifs, on le descendra jusqu'à ce que la propriété d'ordre soit vérifiée.

En utilisant l'implémentation précédente d'un tas, écrire une fonction tri_par_tas qui prend en argument une liste l et renvoie une nouvelle liste, triée. Quelle est la complexité ?

1.4. Exercices

Pour chaque exercice suivant, une des trois structures de données théoriques introduites est judicieuse pour minimiser la complexité. On pourra librement utiliser une fonction peek qui renvoie le prochain élément qui sera retiré de la structure, sans la modifier.

Écrire une fonction parenthésages qui prend en argument une chaîne de caractères s contenant des parenthèses ouvrantes et fermantes comme s = "(()((()())))" et qui renvoie une liste des couples (i,j) où i est l'indice d'une parenthèse ouvrante, et j de la parenthèse fermante. Si la chaîne s est mal parenthésée, on renverra None.

Écrire une fonction qui prend en argument un entier $n$ et renvoie la liste triée de tous les entiers $\leq n$ qui n'ont pas d'autre facteur premier que $2, 3$ et $5$.

Deux équipes d'individus sont représentées par deux files, chaque individu ayant une certaine force. Les deux équipes s'affrontent avec des duels successifs. Lorsque deux indi files s'affrontent, celui avec la plus grande force gagne, et sa force diminue de $1$. Celui avec la plus faible force perd, sa force diminue de $2$, et il retourne à la queue de la file. En cas d'égalité, les deux forces sont diminuées de $1$ et les deux individus retournent à la queue de leur files. Quand la force d'un individu atteint $0$, il est éliminé.

Implémenter une fonction affronte qui prend en argument deux listes, contenant les forces des individus de chaque équipe dans l'ordre dans lequel ils sont enfilés, et qui renvoie 1 ou 2 selon l'équipe qui gagne.

Étant donné une liste l de longueur $n$ et un entier k, on veut renvoyer la liste des maximums des $n-k+1$ tranches l[i:i+k], avec une complexité en $O(n)$ (indépendante de $k$).

2. Parcours en largeur d'un graphe

2.1. Rappels sur le parcours en profondeur

Les extraits suivants implémentent un parcours en profondeur d'un graphe représenté par ses listes d'adjacence, issu d'un sommet d.

def parcours_profondeur(g, d):
    vus = [d]
    a_t = [d] # À traiter
    while a_t != []:
        s = a_t.pop()
        print(s)
        for v in g[s]:
            if v not in vus:
                vus.append(v)
                a_t.append(v)

def parcours_profondeur(g, d):
    # On marque d comme vu
    vus = {d: None}
    a_t = [d]
    while a_t != []:
        s = a_t.pop()
        print(s)
        for v in g[s]:
            if not(v in vus):
                vus[v] = None
                a_t.append(v)

def parcours_profondeur(g, d):
    vus = [d]
    # Fonction auxiliaire récursive
    def traite(s):
        print(s)
        for v in g[s]:
            if v not in vus:
                vus.append(v)
                traite(v)
    traite(d)

2.2. Parcours en largeur

Dans les implémentations itératives du parcours en profondeur, la liste a_traiter est utilisée comme une Pile. En remplaçant cette pile par une file, on obtient un parcours en largeur.

En utilisant le module collections.deque, implémenter une fonction parcours_largeur qui affiche les sommets dans l'ordre dans lequel ils sont visités.
Décrire l'ordre du parcours en largeur pour le graphe ci-contre, en partant du sommet $A$.
★ Écrire une version du parcours en largeur sans utiliser de file. On pourra utiliser deux boucles imbriquées pour traiter les sommets par paquets, selon leur profondeur.
★ Écrire une version récursive du parcours en largeur.

En utilisant les bonnes structures de données, la complexité du parcours en largeur est en $O(n+m)$, où $n$ est le nombre de sommets du graphes, et $m$ le nombre d'arêtes.

En utilisant un parcours en largeur, écrire une fonction existe_chemin qui prend en argument un graphe et deux sommets du graphe et renvoie True si et seulement si il existe un chemin du premier sommet au second.

Pour cette question, un parcours en profondeur fonctionne également.
Écrire une fonction distance avec les mêmes arguments et qui renvoie la distance entre les deux sommets, c'est-à-dire le nombre d'arêtes d'un chemin minimal entre les deux sommets s'il en existe un, et None s'il n'en existe pas.
Écrire une fonction chemin_min avec les mêmes arguments qui renvoie un chemin de longueur minimal entre les deux sommets, sous la forme d'une liste de sommets, ou None s'il n'en existe pas.

Un graphe non orienté est dit biparti si l'ensemble $S$ de ses sommets peut être partitionné en la réunion de deux ensembles $S_1, S_2$ tels que toutes les arêtes de $G$ joignent un sommet de $S_1$ à un sommet de $S_2$. Autrement dit, un graphe $G$ est biparti s'il est $2$−coloriable.

Écrire une fonction est_bipartite qui prend en argument un graphe $G$ supposé connexe et renvoie True si et seulement s'il est biparti.